/**
 * 二叉树
 * 二叉树节点没有value，只有key，实现功能时在外部建立字典 没必要污染二叉树
 * @author doudou
 * @date 2023.06.08
 */
export class BinaryTreeNode{
    public key:number;
    public left:BinaryTreeNode = null;
    public right:BinaryTreeNode = null;
    public value:any;
    public constructor(key:number,value:any){
        this.key = key;
        this.value = value;
    }
}
export enum Compare{
    LESS_THAN = 0,
    BIGGER_THAN = 1,
    EQUAL = 0
}
export function defaultCompare(n1:number,n2:number):Compare{
    return n1 == n2 ? Compare.EQUAL : n1 > n2 ? Compare.BIGGER_THAN : Compare.LESS_THAN
}
export class BinaryTree{
    /**根节点 */
    private root:BinaryTreeNode = null;
    /**比较函数 */
    private compareFn:(n1:number,n2:number)=>Compare;
    constructor(compare = defaultCompare){
        this.compareFn = compare;
        this.root = null;
    }
    /**
     * 插入节点
     * @param key 
     * @param value 
     */
    public insert(key:number,value:any){
        this.insertNode(this.root,new BinaryTreeNode(key, value));
    }
    /**
     * 根据节点插入节点
     * @param target 
     * @param node 
     */
    public insertNode(target:BinaryTreeNode,node:BinaryTreeNode){
        if(this.compareFn(node.key,target.key) === Compare.LESS_THAN){
            if(target.left == null){
                target.left = node;
            } else {
                this.insertNode(target.left,node);
            }
        } else if(this.compareFn(node.key,target.key) === Compare.BIGGER_THAN){
            if(target.right == null){
                target.right = node;
            } else {
                this.insertNode(target.right,node);
            }
        } else {
            throw "插入的节点key相似" + node.key;
        }
    }
    public search(key:number):BinaryTreeNode{
        return this.searchNode(this.root,key)
    }
    public searchNode(node:BinaryTreeNode,key:number):BinaryTreeNode{
        if(node === undefined){
            return null;
        }
        if(this.compareFn(node.key,key) === Compare.LESS_THAN){
            return this.searchNode(node.left,key);
        } else if(this.compareFn(node.key,key) === Compare.BIGGER_THAN){
            return this.searchNode(node.right,key);
        } else {
            return node;
        }
    }
    /**
     * 删除节点
     * @param key 
     */
    public remove(key:number):void{
        this.root = this.removeNode(this.root,key)
    }
    /**
     * 删除一个节点
     * @param node 
     * @param key 
     * @returns 
     */
    public removeNode(node:BinaryTreeNode,key:number):BinaryTreeNode{
        if(this.compareFn(node.key,key) === Compare.LESS_THAN){
            node.left = this.removeNode(node.left,key);
            return node;
        } else if(
            this.compareFn(node.key,key) === Compare.BIGGER_THAN
        ){
            node.right = this.removeNode(node.right,key);
            return node;
        } else {
            if(node.left === undefined && node.right === undefined){
                node = null;
                return node;
            }
            if(node.left === undefined){
                node = node.right
                return node;
            } else if(node.right === undefined){
                node = node.left
                return node;
            }
            let aux = this.minNode(node.right);
            aux.right = this.removeNode(node.right,aux.key);
            aux.left = node.left;
            return aux;
        }

    }
    /**
     * 获取最小节点
     * @returns 
     */
    public min():BinaryTreeNode{
        return this.minNode(this.root)
    }
    /**
     * 根据node 获取最小节点
     * @param node 
     * @returns 
     */
    public minNode(node:BinaryTreeNode):BinaryTreeNode{
        let currentNode = node;
        while(currentNode !== undefined && currentNode.left !== undefined){
            currentNode = currentNode.left
        }
        return currentNode;
    }
    /**
     * 最大节点
     * @returns 
     */
    public max():BinaryTreeNode{
        return this.maxNode(this.root);
    }
    /**
     * 根据node获取最大节点
     * @param node 
     * @returns 
     */
    public maxNode(node:BinaryTreeNode):BinaryTreeNode{
        let currentNode = node;
        while(currentNode !== undefined && currentNode.right !== undefined){
            currentNode = currentNode.right
        }
        return currentNode;
    }
    /**
     * 中序遍历
     * @param callback 
     */
    public inorderTraverse(callback:(node:BinaryTreeNode)=>void){
        this.inOrderTraverseNode(this.root,callback)
    }
    /**
     * 先序
     * @param callback 
     */
    public preOrderTraverse(callback:(node:BinaryTreeNode)=>void){
        this.preOrderTraverseNode(this.root,callback)
    }
    /**
     * 后序
     * @param callback 
     */
    public postOrderTraverse(callback:(node:BinaryTreeNode)=>void){
        this.postOrderTraverseNode(this.root,callback);
    }
    /**
     * 中序遍历
     * 用于排序
     */
    public inOrderTraverseNode(node:BinaryTreeNode,callback:(args:BinaryTreeNode)=>void):void{
        if(!node){
            return;
        }
        this.inOrderTraverseNode(node.left,callback);
        callback(node);
        this.inOrderTraverseNode(node.right,callback);
    }
    /**
     * 先序遍历
     * 用于输出目录结构
     */
    public preOrderTraverseNode(node:BinaryTreeNode,callback:(node:BinaryTreeNode)=>void){
        if(!node){
            return;
        }
        callback(node);
        this.preOrderTraverseNode(node,callback);
        this.preOrderTraverseNode(node,callback);
    }
    /**
     * 后序遍历
     * 用于统计文件大小
     */
    public postOrderTraverseNode(node:BinaryTreeNode,callback:(node:BinaryTreeNode)=>void){
        if(!node){
            return;
        }
        this.postOrderTraverseNode(node,callback);
        this.postOrderTraverseNode(node,callback);
        callback(node);
    }
}